// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

#define NBUCKETS 29

struct {
  struct spinlock lock;
  struct buf buf[NBUF];             // block[30]
  /** 实则循环双向链表  */
  // Linked list of all buffers, through prev/next. 
  // head.next is most recently used.
  //struct buf head;

  struct buf buckets[NBUCKETS];
  struct spinlock bucketslock[NBUCKETS];

} bcache;


void
binit(void)
{
  struct buf *b;
  /** 在head头插入b  */
  initlock(&bcache.lock, "bcache");
  for (int i = 0; i < NBUCKETS; i++)
  {
    initlock(&bcache.bucketslock[i], "bcache");
    bcache.buckets[i].prev = &bcache.buckets[i];
    bcache.buckets[i].next = &bcache.buckets[i];
  }

  for (b = bcache.buf; b < bcache.buf + NBUF; b++)
  {
    int hash = b->blockno % NBUCKETS;;
    b->next = bcache.buckets[hash].next;
    b->prev = &bcache.buckets[hash];
    initsleeplock(&b->lock, "buffer");
    bcache.buckets[hash].next->prev = b;
    bcache.buckets[hash].next = b;
  }
}


// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  int hash =  blockno % NBUCKETS;
  struct buf *b;

  // 首先获取目标哈希桶的锁
  acquire(&bcache.bucketslock[hash]);

  // 在目标哈希桶中查找缓存块
  for(b = bcache.buckets[hash].next; b != &bcache.buckets[hash]; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->time = ticks;
      b->refcnt++;
      release(&bcache.bucketslock[hash]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 如果在目标哈希桶中找不到缓存块，释放目标哈希桶的锁
  release(&bcache.bucketslock[hash]);

  // 获取全局分配大锁
  acquire(&bcache.lock);

  // 再次获取目标哈希桶的锁
  acquire(&bcache.bucketslock[hash]);

  for(b = bcache.buckets[hash].next; b != &bcache.buckets[hash]; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->time = ticks;
      b->refcnt++;
      release(&bcache.bucketslock[hash]);
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  for(b = bcache.buckets[hash].prev; b != &bcache.buckets[hash]; b = b->prev){
        if(b->refcnt == 0){
          b->dev = dev;
          b->blockno = blockno;
          b->valid = 0;     //important  
          b->refcnt = 1;
          release(&bcache.bucketslock[hash]);
          release(&bcache.lock);
          acquiresleep(&b->lock);
          return b;
        }
  }
  // 如果在目标哈希桶中仍然找不到缓存块，尝试从其他哈希桶中回收一个未使用的缓存块
  for (int i = 0; i < NBUCKETS; i++)
  {
    if(i != hash){
      acquire(&bcache.bucketslock[i]);
      for(b = bcache.buckets[i].prev; b != &bcache.buckets[i]; b = b->prev){
        if(b->refcnt == 0){
          b->dev = dev;
          b->blockno = blockno;
          b->valid = 0;     //important  
          b->refcnt = 1;
          
          // 将b从原有哈希桶中移除
          b->next->prev = b->prev;
          b->prev->next = b->next;
          
          // 将b插入到目标哈希桶中
          b->next = bcache.buckets[hash].next;
          b->prev = &bcache.buckets[hash];
          bcache.buckets[hash].next->prev = b;
          bcache.buckets[hash].next = b;
          
          release(&bcache.bucketslock[i]);
          release(&bcache.bucketslock[hash]);
          release(&bcache.lock);
          acquiresleep(&b->lock);
          return b;
        }
      }
      release(&bcache.bucketslock[i]);
    }
  }

  // 如果没有找到可用的缓存块，释放所有锁并触发 panic
  panic("bget: no buffers");
}
// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  int blockno =  b->blockno % NBUCKETS;
  acquire(&bcache.bucketslock[blockno]);
  b->refcnt--;
    if(b->refcnt == 0){
      /** 将b脱出  */
      b->next->prev = b->prev;
      b->prev->next = b->next;
      
      /** 将b接入  */
      b->next = bcache.buckets[blockno].next;
      b->prev = &bcache.buckets[blockno];
      bcache.buckets[blockno].next->prev = b;
      bcache.buckets[blockno].next = b;
    }
    release(&bcache.bucketslock[blockno]);
}


void
bpin(struct buf *b) {
  int blockno =  b->blockno % NBUCKETS;
  acquire(&bcache.bucketslock[blockno]);
  b->refcnt++;
  release(&bcache.bucketslock[blockno]);
}

void
bunpin(struct buf *b) {
  int blockno =  b->blockno % NBUCKETS;
  acquire(&bcache.bucketslock[blockno]);
  b->refcnt--;
  release(&bcache.bucketslock[blockno]);
}